| Example Program Depth-First Search Depth-first search through a graph. This code example illustrates a depth-first search.
1 |
| 2 | #include <seqan/graph.h>
| 3 | #include <iostream>
| 4 |
| 5 | using namespace seqan;
| 6 |
| 7 |
| 8 | int main()
| 9 | {
| 10 | typedef Graph<Directed<> > TGraph;
| 11 | typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
| 12 | typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
| 13 | typedef Size<TGraph>::Type TSize;
|
14 | TSize numEdges = 8;
| 15 | TVertexDescriptor edges[] = {0,3, 0,1, 1,4, 2,4, 2,5, 3,1, 4,3, 5,5};
| 16 | TGraph g;
| 17 | addEdges(g, edges, numEdges);
| 18 | std::cout << g << ::std::endl;
|
19 | char names[] = {'u', 'v', 'w', 'x', 'y', 'z'};
| 20 | String<char> nameMap;
| 21 | resizeVertexMap(g,nameMap, names);
|
22 | String<unsigned int> predMap;
| 23 | String<unsigned int> discoveryTimeMap;
| 24 | String<unsigned int> finishingTimeMap;
|
25 | depth_first_search(g, predMap, discoveryTimeMap, finishingTimeMap);
|
26 | std::cout << "Depth-First search: " << ::std::endl;
| 27 | typedef Iterator<Graph<>, VertexIterator>::Type TVertexIterator;
| 28 | TVertexIterator it(g);
| 29 | while(!atEnd(it)) {
| 30 | std::cout << "Vertex " << getProperty(nameMap, getValue(it)) << ": ";
| 31 | std::cout << "Discovery time = " << getProperty(discoveryTimeMap, getValue(it)) << ",";
| 32 | std::cout << "Finishing time = " << getProperty(finishingTimeMap, getValue(it)) << ",";
| 33 | typedef Value<String<unsigned int> >::Type TPredVal;
| 34 | TPredVal pre = getProperty(predMap, getValue(it));
| 35 | if (pre != getNilPredecessor(g)) {
| 36 | std::cout << "Predecessor = " << getProperty(nameMap, pre) << ::std::endl;
| 37 | } else {
| 38 | std::cout << "Predecessor = nil" << ::std::endl;
| 39 | }
| 40 | goNext(it);
| 41 | }
| 42 | return 0;
| 43 | }
|
|